{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Ice Cream Bars"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxIceCream"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #雪糕的最大数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。</p>\n",
    "\n",
    "<p>商店中新到 <code>n</code> 支雪糕，用长度为 <code>n</code> 的数组 <code>costs</code> 表示雪糕的定价，其中 <code>costs[i]</code> 表示第 <code>i</code> 支雪糕的现金价格。Tony 一共有 <code>coins</code> 现金可以用于消费，他想要买尽可能多的雪糕。</p>\n",
    "\n",
    "<p><strong>注意：</strong>Tony 可以按任意顺序购买雪糕。</p>\n",
    "\n",
    "<p>给你价格数组 <code>costs</code> 和现金量 <code>coins</code> ，请你计算并返回 Tony 用 <code>coins</code> 现金能够买到的雪糕的 <strong>最大数量</strong> 。</p>\n",
    "\n",
    "<p>你必须使用计数排序解决此问题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>costs = [1,3,2,4,1], coins = 7\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>costs = [10,6,8,7,7,8], coins = 5\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>Tony 没有足够的钱买任何一支雪糕。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>costs = [1,6,3,1,2,5], coins = 20\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>Tony 可以买下所有的雪糕，总价为 1 + 6 + 3 + 1 + 2 + 5 = 18 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>costs.length == n</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= costs[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= coins &lt;= 10<sup>8</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-ice-cream-bars](https://leetcode.cn/problems/maximum-ice-cream-bars/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-ice-cream-bars](https://leetcode.cn/problems/maximum-ice-cream-bars/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2,4,1]\\n7', '[10,6,8,7,7,8]\\n5', '[1,6,3,1,2,5]\\n20']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        sz = len(costs)\n",
    "        i = 0\n",
    "        while i < sz and coins > 0:\n",
    "            cost = costs[i]\n",
    "            if cost <= coins:\n",
    "                coins -= cost\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        res = 0\n",
    "        for i in costs:\n",
    "            if coins>=i:\n",
    "                coins-=i\n",
    "                res+=1\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        i=0\n",
    "        for cost in costs:\n",
    "            coins -= cost\n",
    "            if coins>=0:\n",
    "                i += 1\n",
    "            else:\n",
    "                return i\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "\n",
    "        \n",
    "        costs.sort()\n",
    "        sum = 0\n",
    "        num = 0\n",
    "        for i in costs:\n",
    "            if i <= coins:\n",
    "                coins -= i\n",
    "                num += 1\n",
    "            else:\n",
    "                break\n",
    "                \n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        t = 0\n",
    "        for j in costs:\n",
    "            if coins >= j:\n",
    "                t+=1\n",
    "            else:\n",
    "                break\n",
    "            coins-=j\n",
    "        return t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "\n",
    "        cur_sum = 0\n",
    "        cnt = 0\n",
    "        for cost in costs:\n",
    "            cur_sum += cost\n",
    "            if cur_sum > coins:\n",
    "                break\n",
    "            cnt += 1\n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        n = len(costs)\n",
    "        if coins>=sum(costs):\n",
    "            return n\n",
    "        costs.sort()\n",
    "        i = 0\n",
    "        while i<n and coins >=costs[i]:\n",
    "            coins-=costs[i]\n",
    "            i+=1\n",
    "        return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        n=len(costs)\n",
    "        ans=0\n",
    "        while coins>0 and ans<n:\n",
    "            coins-=costs[ans]\n",
    "            if coins>=0:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        k=10**5+1\n",
    "        t=[0]*k\n",
    "        for cost in costs:\n",
    "            t[cost]+=1\n",
    "        count=0\n",
    "        for i in range(1,k):\n",
    "            if t[i]>0:\n",
    "                for _ in range(t[i]):\n",
    "                    coins-=i\n",
    "                    if coins>=0:\n",
    "                        count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        freq = [0] * 100001\n",
    "        for cost in costs:\n",
    "            freq[cost] += 1\n",
    "        cnt = 0\n",
    "        for i in range(1, 100001):\n",
    "            if coins < i:\n",
    "                break\n",
    "            if freq[i] == 0:\n",
    "                continue\n",
    "            curCnt = min(freq[i], coins // i)\n",
    "            cnt += curCnt\n",
    "            coins -= curCnt * i\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        num = 0\n",
    "        for i in range(0, len(costs) ):\n",
    "            coins = coins - costs[i]\n",
    "            num += 1\n",
    "            if coins < 0:\n",
    "                return num - 1\n",
    "        if coins >= 0:\n",
    "            return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        n=0\n",
    "        for i in costs:\n",
    "            if coins-i>=0:\n",
    "                n+=1\n",
    "                coins-=i\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        nums = 0\n",
    "        costs.sort(reverse = False)\n",
    "        for cost in costs:\n",
    "            if cost > coins:\n",
    "                return nums\n",
    "            else:\n",
    "                coins -= cost\n",
    "                nums += 1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        cnt=0\n",
    "        for v in costs:\n",
    "            if coins-v>=0:\n",
    "                cnt+=1\n",
    "                coins-=v\n",
    "            else: break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\" \n",
    "2023-10-03\n",
    "\n",
    " \"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs = sorted(costs)\n",
    "        count = 0\n",
    "        cur_cost = 0\n",
    "        for c in costs:\n",
    "            if cur_cost + c <= coins:\n",
    "                count += 1\n",
    "                cur_cost += c \n",
    "\n",
    "            else:\n",
    "                return count \n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        ans = 0\n",
    "        costs.sort()\n",
    "        for i in range(len(costs)):\n",
    "            if costs[i] <= coins:\n",
    "                coins -= costs[i]\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "\n",
    "        # 排序\n",
    "        costs.sort()\n",
    "        n = len(costs)\n",
    "        cnt = 0\n",
    "        for i, cost in enumerate(costs):\n",
    "            coins -= cost\n",
    "            if coins < 0:\n",
    "                break\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        res = 0\n",
    "        for cost in costs:\n",
    "            coins -= cost\n",
    "            if coins < 0:\n",
    "                break \n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        s = 0\n",
    "        for i in range(len(costs)):\n",
    "            s += costs[i]\n",
    "            if s > coins:\n",
    "                return i\n",
    "        return len(costs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        ans = 0\n",
    "        n = len(costs)\n",
    "        for i in range(n):\n",
    "            if coins - costs[i] >= 0:\n",
    "                ans += 1\n",
    "                coins -= costs[i]\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        res = 0\n",
    "        for i in costs:\n",
    "            coins -= i \n",
    "            if coins >= 0:\n",
    "                res += 1\n",
    "            else:\n",
    "                return res \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        a=0\n",
    "        costs.sort()\n",
    "        if coins<costs[0]:\n",
    "            return 0\n",
    "        b=len(costs)\n",
    "        for i in range(0,b):\n",
    "            if coins-costs[i]>=0:\n",
    "                a=a+1\n",
    "                coins=coins-costs[i]\n",
    "                if i==b-1:\n",
    "                    return a\n",
    "            else:\n",
    "                return a\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        n = len(costs)\n",
    "        costs.sort()\n",
    "        left = 0\n",
    "        cost = 0\n",
    "        while left < n:\n",
    "            cost += costs[left]\n",
    "            if cost <= coins:\n",
    "                left += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs = sorted(costs)\n",
    "        # def func(costs, coins):\n",
    "        #     if len(costs) > 0 and coins >= costs[0]:\n",
    "        #         return 1 + func(costs[1:], coins - costs[0])\n",
    "        #     return 0\n",
    "        \n",
    "        # return func(costs, coins)\n",
    "        ans = 0\n",
    "        i = 0 \n",
    "        while i < len(costs) and coins > 0:\n",
    "            if costs[i] <= coins:\n",
    "                coins -= costs[i]\n",
    "                i += 1\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        count = 0\n",
    "        for cost in costs:\n",
    "            if coins < cost:\n",
    "                return count\n",
    "            coins -= cost\n",
    "            count += 1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        n = len(costs)\n",
    "        costs.sort()\n",
    "        ans = 0\n",
    "        for c in costs:\n",
    "            if coins >= c:\n",
    "                coins -= c\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        ret = 0\n",
    "        for index, cost in enumerate(costs):\n",
    "            coins -= cost\n",
    "            if coins < 0:\n",
    "                break\n",
    "            ret += 1\n",
    "        return ret        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        i = 0\n",
    "        rs = 0\n",
    "        while coins > 0 and i < len(costs):\n",
    "            if costs[i] <= coins:\n",
    "                rs += 1\n",
    "                coins -= costs[i]\n",
    "            else:\n",
    "                break\n",
    "            i += 1\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        res=0\n",
    "        for cost in costs:\n",
    "            if cost<=coins:\n",
    "                res+=1\n",
    "                coins-=cost\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        #排序贪心即可\n",
    "        costs.sort()\n",
    "        cnt=0\n",
    "        for v in costs:\n",
    "            if coins-v>=0:\n",
    "                cnt+=1\n",
    "                coins-=v\n",
    "            else: break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        costs.sort()\n",
    "        while coins >= 0 and i < len(costs):\n",
    "            coins -= costs[i]\n",
    "            if coins >= 0:\n",
    "                ans += 1\n",
    "            i += 1\n",
    "            '''        if coins > costs[-1]:\n",
    "            ans += 1\n",
    "            '''\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        count = 0\n",
    "        num = 0\n",
    "        for i in costs:\n",
    "            count += i\n",
    "            if count <= coins:\n",
    "                num += 1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        idx = 0\n",
    "        while True:\n",
    "            if idx == len(costs):\n",
    "                break\n",
    "            if coins >= costs[idx]:\n",
    "                coins -= costs[idx]\n",
    "                idx += 1\n",
    "            else:\n",
    "                break\n",
    "        return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        num = 0\n",
    "        list_costs = sorted(costs)\n",
    "        for i in list_costs:\n",
    "            coins = coins - i\n",
    "            if coins>=0 :\n",
    "                num +=1\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        min_c = min(costs)\n",
    "        max_c = max(costs)\n",
    "        cot = [0]*(max_c-min_c+1)\n",
    "        # 下标i 转换到价格就是 i+min_c, 价格到下标就是 m - min_c\n",
    "        for c in costs:\n",
    "            cot[c-min_c] += 1\n",
    "        total = 0\n",
    "        remain = coins\n",
    "        for i in range(len(cot)):\n",
    "            if remain==0:\n",
    "                break\n",
    "            if cot[i]>0:\n",
    "                if remain>=cot[i]*(i+min_c):\n",
    "                    remain -= cot[i]*(i+min_c)\n",
    "                    total += cot[i]\n",
    "                else:\n",
    "                    total += (remain//(i+min_c))\n",
    "                    break\n",
    "        return total\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        cnt=0\n",
    "        for v in costs:\n",
    "            if coins-v>=0:\n",
    "                cnt+=1\n",
    "                coins-=v\n",
    "            else: break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        max_val = max(costs)\n",
    "        cnt = [0] * (max_val+1)\n",
    "        ans = 0\n",
    "        for c in costs:\n",
    "            cnt[c] += 1\n",
    "        for i in range(1, max_val+1):\n",
    "            if coins >= i:\n",
    "                cur_cnt = min(cnt[i], coins//i)\n",
    "                ans += cur_cnt\n",
    "                coins -= i*cur_cnt\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        # if not costs:\n",
    "\n",
    "        costs.sort()\n",
    "        sum = 0 \n",
    "        left = 0\n",
    "        for left in range(len(costs)):  # 1 1 2 3\n",
    "            sum+=costs[left]\n",
    "            if sum > coins:\n",
    "                print(left)\n",
    "                return left\n",
    "        \n",
    "        if left==len(costs)-1:\n",
    "            print(len(costs))\n",
    "            return len(costs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        # def countingSort(lst: list[int]) -> list[int]:\n",
    "        #     _max, _min = lst[0], lst[0]\n",
    "        #     for _, _num in enumerate(lst):\n",
    "        #         if _num > _max:\n",
    "        #             _max = _num\n",
    "        #         if _num < _min:\n",
    "        #             _min = _num\n",
    "        #     temp_dict = {num: 0 for num in range(_min, _max + 1)}\n",
    "        #     for _, _num in enumerate(lst):\n",
    "        #         temp_dict[_num] += 1\n",
    "        #     temp_dict = {\n",
    "        #         _key: temp_dict[_key]\n",
    "        #         for _key in temp_dict.keys()\n",
    "        #         if temp_dict[_key] != 0\n",
    "        #     }\n",
    "        #     sorted_lst = []\n",
    "        #     for _key in temp_dict.keys():\n",
    "        #         sorted_lst += [_key for _ in range(temp_dict[_key])]\n",
    "        #     return sorted_lst\n",
    "\n",
    "        # costs = countingSort(costs)\n",
    "        costs = sorted(costs)\n",
    "        i, cnt = 0, 0\n",
    "        while True:\n",
    "            if i == len(costs) or coins < costs[i]:\n",
    "                break\n",
    "            else:\n",
    "                coins -= costs[i]\n",
    "                i += 1\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        n=len(costs)\n",
    "        ans=0\n",
    "        while coins>0 and ans<n:\n",
    "            coins-=costs[ans]\n",
    "            if coins>=0:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        res = 0\n",
    "        for i in costs:\n",
    "            if coins < i:\n",
    "                break\n",
    "            coins -= i\n",
    "            res += 1\n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        p = 0\n",
    "        ret = 0\n",
    "        while coins > 0 and p < len(costs):\n",
    "            c = costs[p]\n",
    "            p += 1\n",
    "            coins -= c\n",
    "            if coins >=0:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while i<len(costs) and coins>0:\n",
    "            if coins>=costs[i]:\n",
    "                coins -= costs[i]\n",
    "                ans += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        ans = 0\n",
    "        costs.sort()\n",
    "        for x in costs:\n",
    "            if coins <= 0 or x > coins:\n",
    "                break\n",
    "            ans += 1\n",
    "            coins -= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        ans = 0\n",
    "        for i, x in enumerate(costs):\n",
    "            if x <= coins:\n",
    "                coins -= x\n",
    "                ans += 1\n",
    "                continue\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        #贪心 + 排序\n",
    "        costs.sort()\n",
    "        x = 0\n",
    "        for i in range (len(costs)):\n",
    "            if coins >= costs[i]:\n",
    "                coins -= costs[i]\n",
    "                x += 1\n",
    "            else:\n",
    "                break\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        res = 0\n",
    "        costs.sort()\n",
    "        print(costs)\n",
    "        for i in costs:\n",
    "            if coins >= i:\n",
    "                res = res+1\n",
    "                coins = coins -i\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "\n",
    "        \n",
    "        costs.sort()\n",
    "        sum = 0\n",
    "        \n",
    "        num = 0\n",
    "        for i in costs:\n",
    "            if sum + i <= coins:\n",
    "                sum += i\n",
    "                num += 1\n",
    "            else:\n",
    "                break\n",
    "                \n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        # def countingSort(lst: list[int]) -> list[int]:\n",
    "        #     _max, _min = lst[0], lst[0]\n",
    "        #     for _, _num in enumerate(lst):\n",
    "        #         if _num > _max:\n",
    "        #             _max = _num\n",
    "        #         if _num < _min:\n",
    "        #             _min = _num\n",
    "        #     temp_dict = {num: 0 for num in range(_min, _max + 1)}\n",
    "        #     for _, _num in enumerate(lst):\n",
    "        #         temp_dict[_num] += 1\n",
    "        #     temp_dict = {\n",
    "        #         _key: temp_dict[_key]\n",
    "        #         for _key in temp_dict.keys()\n",
    "        #         if temp_dict[_key] != 0\n",
    "        #     }\n",
    "        #     sorted_lst = []\n",
    "        #     for _key in temp_dict.keys():\n",
    "        #         sorted_lst += [_key for _ in range(temp_dict[_key])]\n",
    "        #     return sorted_lst\n",
    "\n",
    "        # costs = countingSort(costs)\n",
    "        costs = sorted(costs)\n",
    "        i, cnt = 0, 0\n",
    "        while True:\n",
    "            if i == len(costs) or coins < costs[i]:\n",
    "                break\n",
    "            else:\n",
    "                coins -= costs[i]\n",
    "                i += 1\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "\n",
    "        \n",
    "        costs.sort()\n",
    "        sum = 0\n",
    "        num = 0\n",
    "        for i in costs:\n",
    "            if i <= coins:\n",
    "                coins -= i\n",
    "                num += 1\n",
    "            else:\n",
    "                break\n",
    "                \n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        idx = 0\n",
    "        while coins > 0 and idx < len(costs) and costs[idx] <= coins:\n",
    "            coins -= costs[idx]\n",
    "            idx += 1\n",
    "        return idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs=sorted(costs)\n",
    "        res = 0\n",
    "        a = []\n",
    "        if sum(costs) <= coins:\n",
    "            return len(costs)\n",
    "        if min(costs) > coins:\n",
    "            return 0\n",
    "        for i in range(len(costs)):\n",
    "            res += costs[i]\n",
    "            if res <= coins:\n",
    "                a.append(costs[i])\n",
    "            else:\n",
    "                break\n",
    "        result = len(a)\n",
    "        return result \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        ans = 0\n",
    "        for i in costs:\n",
    "            if i <= coins:\n",
    "                coins -= i\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        bucket = [0] * (max(costs) + 1)\n",
    "        for c in costs:\n",
    "            bucket[c] += 1\n",
    "        ans = 0\n",
    "        for i, cnt in enumerate(bucket):\n",
    "            while cnt > 0 and coins >= i:\n",
    "                coins -= i\n",
    "                cnt -= 1\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(costs)):\n",
    "            coins -= costs[i]\n",
    "            if coins < 0:\n",
    "                return ans\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        ans = 0\n",
    "        for c in costs:\n",
    "            coins -= c\n",
    "            if coins >= 0:\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        k=10**5+1\n",
    "        t=[0]*k\n",
    "        for cost in costs:\n",
    "            t[cost]+=1\n",
    "        count=0\n",
    "        for i in range(1,k):\n",
    "            if t[i]>0:\n",
    "                for _ in range(t[i]):\n",
    "                    coins-=i\n",
    "                    if coins>=0:\n",
    "                        count+=1\n",
    "                    else:\n",
    "                        return count\n",
    "        return count\n",
    "\n",
    "class Solution2:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        count=0\n",
    "        for c in costs:\n",
    "            coins-=c\n",
    "            if coins>=0:\n",
    "                count+=1\n",
    "            else:\n",
    "                return count\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        res=0\n",
    "        for cost in costs:\n",
    "            if cost<=coins:\n",
    "                res+=1\n",
    "                coins-=cost\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        min_ele, max_ele = float('inf'), 0\n",
    "        for n in costs:\n",
    "            min_ele = min(min_ele, n)\n",
    "            max_ele = max(max_ele, n)\n",
    "\n",
    "        n = max_ele - min_ele + 1\n",
    "        counter = [0 for _ in range(n)]\n",
    "\n",
    "        for n in costs:\n",
    "            counter[n - min_ele] += 1\n",
    "\n",
    "        ans = 0\n",
    "        for i, n in enumerate(counter):\n",
    "            while n > 0 and coins - (i + min_ele) >= 0:\n",
    "                coins = coins - (i + min_ele)\n",
    "                ans += 1\n",
    "                n -= 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = Solution()\n",
    "    print(s.maxIceCream([1, 3, 2, 4, 1], 7))\n",
    "    print(s.maxIceCream([10, 6, 8, 7, 7, 8], 5))\n",
    "    print(s.maxIceCream([4, 7, 6, 4, 4, 2, 2, 4, 8, 8], 41))\n",
    "    print(s.maxIceCream([1, 6, 3, 1, 2, 5], 20))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        total_cost = 0\n",
    "\n",
    "        for i,val in enumerate(costs):\n",
    "            total_cost = total_cost+val\n",
    "            if total_cost>coins:\n",
    "                return i\n",
    "        return len(costs)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        buy = []\n",
    "        h = coins\n",
    "        max_c = 0\n",
    "        for c in costs:\n",
    "            if c <= h:\n",
    "                max_c = max(c, max_c)\n",
    "                buy.append(c)\n",
    "                h -= c\n",
    "                continue\n",
    "            if c > h:\n",
    "                if c < max_c:\n",
    "                    buy.pop(buy.index(max_c))\n",
    "                    buy.append(c)\n",
    "                    h = h+max_c-c\n",
    "                    max_c = max(buy)\n",
    "        return len(buy)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, a: List[int], b: int) -> int:\n",
    "        a.sort(reverse=True)\n",
    "        ans = 0\n",
    "        while a and b:\n",
    "            c = a.pop() \n",
    "            if b>=c:\n",
    "                b -= c\n",
    "                ans += 1\n",
    "            else:\n",
    "                return ans \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        heapq.heapify(costs)\n",
    "        ans = 0\n",
    "        while coins and costs:\n",
    "            if coins < costs[0]:\n",
    "                break\n",
    "            coins -= heapq.heappop(costs)\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        a=max(costs)\n",
    "        cur=[0 for i in range(a)]\n",
    "        for i in costs:\n",
    "            cur[i-1]+=1\n",
    "        ans=[]\n",
    "        for i in range(a):\n",
    "            ans.extend([i+1]*cur[i])\n",
    "        count=0\n",
    "        for i in ans:\n",
    "            coins -=i\n",
    "            if coins <0:\n",
    "                return count\n",
    "            else:\n",
    "                count +=1\n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        max_val = max(costs)\n",
    "        cnt = [0] * (max_val+1)\n",
    "        ret = [0] * len(costs)\n",
    "        ans = 0\n",
    "        for c in costs:\n",
    "            cnt[c] += 1\n",
    "        # 对 count 数组进行累加操作\n",
    "        for i in range(1, len(cnt)):\n",
    "            cnt[i] += cnt[i - 1]\n",
    "        for num in reversed(costs):\n",
    "            ret[cnt[num]-1] = num\n",
    "            cnt[num] -= 1\n",
    "        for r in ret:\n",
    "            if coins >= r:\n",
    "                coins -= r\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "\n",
    "        s1 = sorted(costs)\n",
    "        print(s1)\n",
    "        cnt = 0\n",
    "        cost = 0\n",
    "        for ii in range(len(s1)):\n",
    "            cost += s1[ii]\n",
    "            if cost <= coins:\n",
    "                cnt += 1\n",
    "        \n",
    "        print(cnt)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        costs.sort()\n",
    "        for i in range(1,len(costs)):\n",
    "            costs[i] += costs[i-1]\n",
    "        return bisect_right(costs,coins)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        return bisect_right(list(accumulate(sorted(costs))), coins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        t=[0]\n",
    "        for i,c in enumerate(sorted(costs)):t.append(t[-1]+c)\n",
    "        return bisect.bisect_right(t[1:],coins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "\n",
    "        cnt = Counter(costs)\n",
    "\n",
    "        sorted_keys = list(cnt.keys())\n",
    "        sorted_keys.sort()\n",
    "\n",
    "        ans = 0\n",
    "        for k in sorted_keys:\n",
    "            if coins == 0:break\n",
    "            c = min(coins // k, cnt[k])\n",
    "            coins -= c * k\n",
    "            ans += c\n",
    "        \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        cnt = Counter(costs)\n",
    "        res = 0\n",
    "        for c in range(1, 10 ** 5 + 1):\n",
    "            x = min(coins // c, cnt[c])\n",
    "            res += x\n",
    "            coins -= x * c\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxIceCream(self, costs: List[int], coins: int) -> int:\n",
    "        c = Counter(costs)\n",
    "        cnt = 0 \n",
    "        \n",
    "        for k in sorted(list(c.keys())):\n",
    "            v = c[k]\n",
    "            if coins <= v*k:\n",
    "                cnt += coins//k \n",
    "                coins  = 0\n",
    "                break\n",
    "            else:\n",
    "                cnt += v \n",
    "                coins -= v*k \n",
    "        return cnt"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
